/**
* @description: 983. 最低票价
* @author hewei
* @date 2022/9/29 16:54
* @version 1.0
*/

public class MincostTickets {

    public static void main(String[] args) {
        int[] nums = {4,5,9,11,14,16,17,19,21,22,24};
        int[] costs = {1,4,18};
        System.out.println(new MincostTickets().mincostTickets(nums, costs));
    }

    public int mincostTickets1(int[] days, int[] costs) {
        int n = days.length;
        int[][] dp = new int[n][3];
        dp[0][0] = costs[0];
        dp[0][1] = costs[1];
        dp[0][2] = costs[2];
        int qi = days[0];
        int sanShi = days[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.min(dp[i - 1][0], Math.min(dp[i - 1][1], dp[i - 1][2])) + costs[0];
            if (qi + 6 >= days[i]) {
                dp[i][1] = dp[i - 1][1];
            } else {
                int index = i;
                while (days[index] + 6 >= days[i]) --index;
                qi = days[index + 1];
                dp[i][1] = Math.min(dp[index][0], Math.min(dp[index][1], dp[index][2])) + costs[1];
            }
            if (sanShi + 29 >= days[i]) {
                dp[i][2] = dp[i - 1][2];
            } else {
                int index = i;
                while (days[index] + 29 >= days[i]) --index;
                sanShi = days[index + 1];
                dp[i][2] = Math.min(dp[index][0], Math.min(dp[index][1], dp[index][2])) + costs[2];
            }
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }

    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int[] dp = new int[days[n - 1] + 1];
        for (int i = 1, index = 0; i < dp.length; i++) {
            int x, y, z;
            if (i == days[index]) {
                x = dp[i - 1] + costs[0];
                ++index;
            } else x = dp[i - 1];
            y = (i > 7 ? dp[i - 7] : dp[0]) + costs[1];
            z = (i > 30 ? dp[i - 30] : dp[0]) + costs[2];
            dp[i] = Math.min(x, Math.min(y, z));
        }
        return dp[dp.length - 1];
    }
}
